#include "myTree.h"

using namespace std;

void TreeNode::printNode()
{
    cout << this->data;
}

/********************************TreeNode************************************/

TreeNode::TreeNode(char d, TreeNode *lc, TreeNode *rc, NodeTag lt, NodeTag rt)
{
    this->data = d;
    this->leftChild = lc;
    this->rightChild = rc;
    this->lTag = lt;
    this->rTag = rt;
}

TreeNode::~TreeNode()
{
}

/*********************************MyTree*************************************/
MyTree::MyTree() // 无参构造
{
    this->root = nullptr;
    this->isThread = false;
}

MyTree::MyTree(const char *c) // 构造函数
{
    int i = 0;
    root = createTree(c, &i);
    isThread = false;
}

MyTree::MyTree(const MyTree &T) // 拷贝函数
{
    root = copyTree(T.root);
    isThread = T.isThread;
}

MyTree::~MyTree() // 析构函数
{
}

void MyTree::preOrderTraverse() // 前序遍历
{
    TreeNode *tmp = root;
    if (this->isThread == false)
    {
        preOrder(tmp);
    }
}

void MyTree::inOrderTraverse() // 中序遍历
{
    TreeNode *tmp = root;
    if (this->isThread == false)
    {
        inOrder(tmp);
    }
    else
    {
        inOrderTraverse_Thr(tmp);
        // inOrder(tmp);
    }
}

void MyTree::postOrderTraverse() // 后序遍历
{
    if (this->isThread == false)
    {
        TreeNode *tmp = root;
        postOrder(tmp);
    }
}

int MyTree::countLeaf() // 叶结点计数
{
    if (this->isThread == false)
    {
        TreeNode *tmp = root;
        return leafNum(tmp);
    }
    return 0;
}

int MyTree::countHeight() // 计算树的深度
{
    if (this->isThread == false)
    {
        TreeNode *tmp = root;
        return height(tmp);
    }
    return 0;
}

bool MyTree::isThreadedTree() // 判断是否为线索二叉树
{
    return this->isThread;
}

bool MyTree::inOrderThreading() // 线索化
{
    this->isThread = true;
    TreeNode *tmp = root;
    inThreading(tmp);
    return this->isThread;
}

TreeNode &MyTree::locateNode(const char &d) // 结点定位
{
    TreeNode *tmp = root;
    return *locate(tmp, d);
}

TreeNode &MyTree::preNode(const TreeNode &node) // 获取前驱结点
{
    TreeNode *p = node.leftChild;
    if (this->isThread == false)
    {
        this->inOrderThreading();
    }
    // 如果ltag=0，则p的后继为以该节点为根的左子树上按中序遍历的最后一个节点
    if (node.lTag == Link)
    {
        return *(inOrderLastNode(p));
    }
    else
        return *(node.leftChild);
}

TreeNode &MyTree::nextNode(const TreeNode &node) // 获取后继结点
{
    TreeNode *p = node.rightChild;

    if (this->isThread == false)
    {
        this->inOrderThreading();
    }
    // 如果rtag=0，则p的后继为以该节点为根的右子树上按中序遍历的第一个节点
    if (node.rTag == Link)
    {
        return *(inOrderFisrtNode(p));
    }
    else
        return *(node.rightChild);
}

/****************************Helper function*****************************************/

TreeNode *MyTree::createTree(const char str[], int *i)
{
    if (str[*i] == '\0' || str[*i] == '@')
    {
        return nullptr;
    }
    else
    {
        TreeNode *p = new TreeNode(str[*i], nullptr, nullptr, Link, Link);
        ++(*i);
        p->leftChild = createTree(str, i);
        ++(*i);
        p->rightChild = createTree(str, i);
        return p;
    }
}

TreeNode *MyTree::copyTree(TreeNode *node)
{
    if (!node)
    {
        return nullptr;
    }

    TreeNode *newNode = new TreeNode(node->data, nullptr, nullptr, Link, Link);
    if (node->leftChild)
    {
        newNode->leftChild = copyTree(node->leftChild);
    }
    else
        newNode->leftChild = nullptr;
    if (node->rightChild)
    {
        newNode->rightChild = copyTree(node->rightChild);
    }
    else
        newNode->rightChild = nullptr;
    return newNode;
}

void MyTree::preOrder(TreeNode *node)
{
    if (node)
    {
        node->printNode();
        preOrder(node->leftChild);
        preOrder(node->rightChild);
    }
}

void MyTree::inOrder(TreeNode *node)
{
    if (node)
    {
        inOrder(node->leftChild);
        node->printNode();
        inOrder(node->rightChild);
    }
}

void MyTree::postOrder(TreeNode *node)
{
    if (node)
    {
        postOrder(node->leftChild);
        postOrder(node->rightChild);
        node->printNode();
    }
}

int MyTree::leafNum(TreeNode *node)
{
    if (!node)
    {
        return 0;
    }
    if (!node->leftChild && !node->rightChild)
    {
        return 1;
    }
    return leafNum(node->leftChild) + leafNum(node->rightChild);
}

int MyTree::height(TreeNode *node)
{
    int lch = 1, rch = 1;
    if (!node)
    {
        return 0;
    }
    lch += height(node->leftChild);
    rch += height(node->rightChild);
    return lch > rch ? lch : rch;
}

TreeNode *pre = nullptr;
void MyTree::inThreading(TreeNode *p)
{
    // pre是全局变量，初始化时其右孩子指针为空，便于在树的最左点开始建线索
    if (p != nullptr)
    {
        inThreading(p->leftChild);
        if (p->leftChild == nullptr)
        {
            p->lTag = Thread;
            p->leftChild = pre;
        }
        if (pre != nullptr && pre->rightChild == nullptr)
        {
            pre->rightChild = p;
            pre->rTag = Thread;
        }
        pre = p;
        inThreading(p->rightChild);
    }
}

void MyTree::inOrderTraverse_Thr(TreeNode *node)
{
    TreeNode *p = node;
    if (p)
        while (p->leftChild != nullptr)
            p = p->leftChild;
    TreeNode tmp = *p;
    while (&tmp != nullptr)
    {
        tmp.printNode();
        if (tmp.rightChild != nullptr)
        {
            tmp = this->nextNode(tmp);
        }
        else
            break;
    }
}

TreeNode *MyTree::locate(TreeNode *node, const char &c)
{
    if (node->data == c)
    {
        return node;
    }

    if (node->leftChild && node->lTag != Thread)
    {
        TreeNode *p = locate(node->leftChild, c);
        if (p)
        {
            return p;
        }
    }

    if (node->rightChild && node->rTag != Thread)
    {
        TreeNode *p = locate(node->rightChild, c);
        if (p)
        {
            return p;
        }
    }
    return nullptr;
}

TreeNode *MyTree::inOrderFisrtNode(TreeNode *node)
{
    TreeNode *tmp = node;
    while (tmp->lTag == Link)
    {
        tmp = tmp->leftChild;
    }
    return tmp;
}

TreeNode *MyTree::inOrderLastNode(TreeNode *node)
{
    TreeNode *tmp = node;
    while (tmp->rTag == Link)
    {
        tmp = tmp->rightChild;
    }

    return tmp;
}
/*********************************************************************/

HuffmanTree::HuffmanTree(const int &n, const int *data) // 构造函数
{
    this->num = n;
    this->HFT = new HFNode[n * 2];
    int *p = new int[n];
    for (int i = 0; i < n; i++)
    {
        p[i] = data[i];
    }

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n - i - 1; j++)
        {
            if (p[j] < p[j + 1])
            {
                int tmp = p[j];
                p[j] = p[j + 1];
                p[j + 1] = tmp;
            }
        }
    }
    initleaves(n, p);
    generateCodes(n * 2 - 1, "");
    // showHFT(this->num);
}

HuffmanTree::~HuffmanTree() // 析构函数
{
}

void HuffmanTree::printHuffmanCodes()
{
    int n = this->num;
    for (int j = 1; j <= n; j++)
    {
        cout << HFT[j].weight << ":" << HFT[j].code << endl;
    }
}

// Helper function to delete tree nodes

void HuffmanTree::generateCodes(int idx, string code)
{
    HFT[idx].code = code;
    if (HFT[idx].left != 0)
    {
        generateCodes(HFT[idx].left, code + "0");
    }
    if (HFT[idx].right != 0)
    {
        generateCodes(HFT[idx].right, code + "1");
    }
}

void HuffmanTree::initleaves(int n, const int *data)
{
    if (n <= 1)
        return;
    int m = 2 * n - 1; // 数组共2n - 1个元素
    for (int i = 1; i <= m; i++)
    {
        HFT[i].parent = 0;
        HFT[i].left = 0;
        HFT[i].right = 0;
    }
    for (int i = 1; i <= n; i++)
        HFT[i].weight = data[i - 1];
    for (int i = n + 1; i <= m; i++) // 产生的新结点要放在从n+1开始，一直到2n-1的位置
    {
        int s1, s2;
        selectMin(HFT, i, s1, s2);
        HFT[s1].parent = i;
        HFT[s2].parent = i; // 相当于从表F中删除s1, s2
        HFT[i].left = s1;
        HFT[i].right = s2;
        HFT[i].weight = HFT[s1].weight + HFT[s2].weight;
    }
}

void HuffmanTree::selectMin(HFNode *hft, int n, int &s1, int &s2)
{
    for (int i = 1; i < n; i++)
    { // 初始化s1，s1的双亲为0
        if (HFT[i].parent == 0)
        {
            s1 = i;
            break;
        }
    }

    for (int i = 1; i < n; i++)
    { // s1为权值最小的下标
        if (HFT[i].parent == 0 && HFT[s1].weight > HFT[i].weight)
            s1 = i;
    }

    for (int j = 1; j < n; j++)
    { // 初始化s2，s2的双亲为0
        if (HFT[j].parent == 0 && j != s1)
        {
            s2 = j;
            break;
        }
    }

    for (int j = 1; j < n; j++)
    { // s2为另一个权值最小的下标
        if (HFT[j].parent == 0 && HFT[s2].weight > HFT[j].weight && j != s1)
            s2 = j;
    }
}

void HuffmanTree::showHFT(int n)
{
    cout << "index  weight  parent  LTree  RTree" << endl;
    cout << left; // 左对齐输出
    int m = 2 * n - 1;
    for (int i = 1; i <= m; i++)
    {
        cout << i << "  ";
        cout << HFT[i].weight << "  ";
        cout << HFT[i].parent << "  ";
        cout << HFT[i].left << "  ";
        cout << HFT[i].right << "  ";
        cout << HFT[i].code << "  " << endl;
    }
}
